Conventionally, various image retrieval methods and recognition methods using edge features have been proposed. As an edge extraction method, it is a common practice to make an arithmetic operation for a range including each pixel of interest and its surrounding pixels using a differential filter. As such filter, a Prewitt filter, Sobel filter, Robinson filer, Kirish filter, and the like may be used. When an edge feature is used in, e.g., image retrieval, an edge distribution in an image is extracted as a feature amount in many cases.
An edge histogram in the prior art uses an edge extraction method required to obtain an edge distribution with lower calculation cost than a method using a Sobel filter or the like (see ETRI Journal, Volume 24, Number 1, February 2002 (“Efficient Use of MPEG-7 Edge Histogram Descriptor” Chee Sun Won et al.)).
As shown in FIG. 1A, an input image is divided into 4×4 sub-images. Furthermore, each sub-image is divided into squares (image-blocks), the number of which becomes close to a predetermined value. Next, each image-block is divided into four (=2×2), and the average brightness value of each small region is calculated.
Next, using filters 111 to 115 corresponding to four directions (vertical direction 101, horizontal direction 102, 45° direction 103, and 135° direction 104), and a non-direction 105, edge magnitudes m_v, m_h, m_d45, m_d135, and m_nd are calculated. Let a(n) be the average brightness value of each of four-divided small regions of an image-block. For example, m_v is expressed by:m—v=|1×a(0)+(−1)×a(1)+1×a(2)+(−1)×a(3)|  (1)for n=0 to 3 (n indicates a number assigned to each of four-divided small regions)
When a maximum value of the edge magnitudes (m_v, m_h, m_d45, m_d135, and m_nd) is equal to or larger than a predetermined threshold A, it is determined that the direction of that maximum value is an edge direction of the image-block of interest. The threshold A is a lower limit value of the magnitude that can be considered as the presence of edge. By counting the edge directions of image-blocks included in respective sub-images, edge histograms Eij are calculated (note that i=0 to 4 corresponds to respective filters, and j=0 to 15 corresponds to sub-images). These edge histograms are extracted as a feature amount.
However, the edge extraction method obtained by the above non-patent reference 1 can reduce the calculation cost compared to that using a Sobel filter or the like, but often cannot sufficiently obtain edge features.
A conspicuous example in which edge features cannot be sufficiently obtained will be explained below taking a line image as an example. Depending on locations of image-blocks in a line image, the edge of a line segment of the line image can or cannot be extracted. For example, when a line segment passes through the boundary of image-blocks, as shown in FIG. 9A, it occupies only small areas in the image-blocks. Hence, if the average brightness values are calculated, the influence of the line segment is reduced, and nearly no difference of the average brightness values is generated among small regions, thus failing to extract any edge.
On the other hand, when a line segment falls within half image-blocks, as shown in FIG. 9B, if the average brightness values are calculated, the influence of the line segment is sufficient. Hence, an edge in the vertical direction can be detected. Of course, even in case of FIG. 9A, when the threshold A is decreased, an edge can be detected. However, even a slight average brightness difference is extracted as an edge in turn, and noise or the like is erroneously extracted as an edge.
Image-blocks may often be formed at different positions in images with the same contents. For example, two images include an object (a vase or the like) which appears on a plain background, but they have different object positions. Also, in case of an image stored in a hard disk and an image obtained by scanning the printout of that image using a scanner, image positions shift depending on a position where a paper sheet is placed on the scanner.
Upon comparison of these two images, an edge may be extracted from one image but it may not be extracted from the other image. As a result, these images cannot be determined as identical images.